// https://leetcode.cn/problems/jump-game-ii/description/

// 算法思路总结：
// 1. 使用贪心策略求解最小跳跃次数
// 2. 维护当前跳跃区间，选择下一跳能到达最远的位置
// 3. 每次跳跃选择使后续覆盖范围最大的位置
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int jump(vector<int>& nums) 
    {
        int m = nums.size();
        if (m == 1) return 0;
        
        int ret = 1;
        int l = 0, r = nums[0];

        while (l + r < m - 1)
        {
            int tmpSum = 0, tmpIndex = 0;
            for (int i = 1 ; i <= r ; i++)
            {
                if (i + nums[l + i] > tmpSum)
                {
                    tmpSum = i + nums[l + i];
                    tmpIndex = l + i;
                }                
            }
            l = tmpIndex;
            r = nums[l];
            ret++;
        }

        return ret;
    }
};

int main()
{
    vector<int> v1 = {2,3,1,1,4}, v2 = {2,3,0,1,4};
    Solution sol;

    cout << sol.jump(v1) << endl;
    cout << sol.jump(v2) << endl;

    return 0;
}
